package com.example.demo.algorithm.graph;

import com.example.demo.algorithm.linear.Queue;

/**
 * @Author: xiatian
 * @CreateTime: 2022/2/13 4:33 下午
 * @Description: 加权无向图
 */
public class EdgeWeightedGraph {
    //顶点的数目
    private int V;
    //边的数目
    private int E;
    //邻接表
    private Queue<Edge>[] adj;

    public EdgeWeightedGraph(int V) {
        this.V = V;
        this.E = 0;
        this.adj = new Queue[V];
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new Queue<Edge>();
        }
    }

    //返回顶点的数量
    public int V() {
        return V;
    }

    //返回图中边的数量
    public int E() {
        return E;
    }

    /**
     * 向加权无向图中添加一条边e
     *
     * @param e
     */
    public void addEdge(Edge e) {
        //在无向图中，边是没有方向的，所以该边同时出现在e这个边的两个顶点的领接表中
        int v = e.either();
        int w = e.other(v);
        adj[v].enqueue(e);
        adj[w].enqueue(e);
        //边加一
        E++;
    }

    /**
     * 获取和顶点v关联的所有边
     *
     * @param v
     * @return
     */
    public Queue<Edge> adj(int v) {
        return adj[v];
    }

    /**
     * 获取加权无向图中的所有边
     *
     * @return
     */
    public Queue<Edge> edges() {
        //创建一个队列对象，存储所有的边
        Queue<Edge> allEdges = new Queue<>();
        //遍历图中的每个顶点，找到该顶点的领接表，领接表中存储了该顶点关联的每一条边
        for (int i = 0; i < V; i++) {
            for (Edge e : adj(i)) {
                //因为是无向图，所以同一条边同时出现在了它关联的两个顶点的领接表中，需要让一条边只记录一次
                if (e.other(i) < i) {
                    allEdges.enqueue(e);
                }
            }

        }
        return allEdges;
    }

}
